FIG. 1 depicts a situation where a resource R has authorized party P1 to use the resource—in effect, R has given access authorisation A to P1. P1 can thus contact R and use its capabilities, R allowing access to P1 upon P1 establishing its identity. In addition, R has given P1 the right to pass on (‘delegate’) the authorisation to others—in FIG. 1, P1 is shown as passing authorization A to party P4. When P4 contacts resource R, the latter will require some proof that P4 has indeed been authorised by P1; this proof takes the form of a certificate C1-4 issued by P1 to P4 and provided by P4 to R. In the electronic world this certificate will generally take the form of a digitally-signed document signed by P1 using public-key/private-key cryptographic technology.
For present purposes, it will be assumed that the certificate C1-4 (and the other certificates referred to below) are SPKI-like certificates, though it should be understood that this is not essential for the present invention. SPKI (“Simple Public Key Infrastructure”) certificates are described detail in references [2], [3], [4] listed at the end of this description. FIG. 2 illustrates the main elements of an SPKI-like attribute certificate (as already noted, the term “attribute” is herein used broadly and in relation to SPKI certificates encompasses both “authorization” and “attribute” certificates as defined in the above-referenced documents). The FIG. 2 certificate has fields for specifying the issuer of the certificate (ISSUER), the beneficiary of the certificate (SUBJECT), the attribute being passed to the subject by the certificate (AUTHORIZATION), whether onward delegation of the attribute is permitted (DELGATION), and the limits of validity of the certificate (VALIDITY). An important feature of SPKI-like certificates is that that they are primarily associated with principals that are public keys (or their hashes) rather than with parties identified by distinguished names. Thus, the “issuer” will always be a principal, that is, a public key or its hash); similarly the “subject” can either be a principal or, as will be seen later, a name that can be translated by a name certificate into a principal. Of course, there will be a keyholder who controls the private key associated with the public key forming a principal—however, it is not fundamental that the keyholder is named.
In addition to the above-mentioned fields, certificate C1-4 carries a digital signature formed by using the private key of the issuer.
In relation to the FIG. 1 example, P1 would be keyholder for a first key pair and P4 the keyholder for a second key pair, the “issuer” of the certificate C1-4 then being the public key of the key pair associated with P1 and the “subject” being the public key associated with P4. On receiving the certificate, R checks it by using the digital signature and public key of the issuer. Since R will know the public key of P1 and trust this knowledge (this would be part of the original authorisation of the P1 by R), R can now be sure that the keyholder associated with the public key forming the subject of certificate C1-4 has been duly authorised by P1. R can establish that the party requesting access (P4) is this keyholder by an appropriate challenge-response transaction (in which P4 is required to use its private key to encrypt data sent by R, R then checking the returned encrypted data using the public key for which P4 is supposedly the keyholder).
FIG. 3 illustrates a more complicated situation in which P4 receives authorization A from P1 not directly but through intermediate parties P2 and P3. This time P4 has the following certificates:                C1-2,—the certificate given by P1 to P2 to delegate authorisation A to P2;        C2-3,—the certificate given by P2 to P3 to delegate authorisation A to P3;        C3-4,—the certificate given by P3 to P4 to delegate authorisation A to P4.        
Of course, the parties P1, P2, P3 and P4 are not specified in the certificates directly, the latter referring to public keys KPUB1, KPUB2, KPUB3 and KPUB4 respectively associated with P1, P2, P3, and P4.
P4 when requesting access to resource R passes the latter all three of the above certificates which R checks; R also checks that the party requesting access (P4) is the key holder of public key KPUB4. Thereafter, R has the task of determining whether KPUB4 (P4) has indeed been delegated authorisation A. In other words, R needs to be able to establish a trusted chain of delegations of authorisation A from itself to KPUB4. The first link in this chain is, of course, the delegation by R to KPUB1 and R does not require a certificate to prove this—it is a “trust assumption” of R. R can then see from certificate C1-2 that KPUB1 (P1) has authorised a principal constituted by public key KPUB2 (P2). From certificate C2-3, R can also see that KPUB2 has in turn passed on the authorisation to KPUB3 (P3); finally, C3-4 shows that KPUB3 has passed on authorisation A to KPUB4. By combining the certificates, R can establish the required trust chain from itself to KPUB4 (P4).
In carrying out the above proof, R will also have checked that the “delegation” field of each of the certificates C1-2 and C2-3 permitted onward delegation of authorisation A. Additionally, the validity fields of all three certificates will have been checked.
It is possible that one party in the chain only delegated a subset of the authorisation A (for example, only some of the capabilities of R can be used by the subject of the certificate). R therefore needs to ascertain what is the scope of authorisation reaching KPUB4 (P4) which is done by determining the intersection of the authorisation fields of all the certificates and seeing if this encompasses the requested access.
As noted above, the “subject” of an SPKI-like certificate can be identified by a name rather than a principal; this name will be a local name referred to the name space in which it is defined (so as to provide a fully qualified SDSI name—see references [3] and [6]). The name space identifier starts with the public key of the “issuer” responsible for the space within which the name exists (followed possibly by one or more sub-name spaces identified by name). Where a local name occurs in the “subject” of a certificate, the name space to which it refers is taken to be that of the “issuer” of the certificate. Naming a principal, if done, is primarily done for human convenience whilst SPKI processing systems fundamentally work with principals. The mapping between a name and the corresponding principal is done using a name certificate. FIG. 3 depicts an SPKI name certificate and, as can be seen, the certificate has four fields that specify the principal who is the issuer of the certificate (ISSUER), the name being assigned in the name space of the issuer(NAME), the subject being named (SUBJECT), and the validity limits of the certificate (VALIDITY). The name certificate also carries a digital signature, formed using the private key associated with the issuer.
In the most straightforward case, the subject will be aprincipal so that the certificate maps a name in the issuer's name space to a corresponding public key (or its hash)—this is the case illustrated in FIG. 3 where the local name “name” that forms the content of the field NAME is depicted as combining with the public key of the issuer KPUB—issuer issuer to map to the public key KPUB—subject in the SUBJECT field. The subject may, however, alternatively be a fully qualified SDSI name.
In determining whether a trust chain exists, it may be necessary to use a name certificate to map an authorisation given to a named subject to the corresponding principal.
A more formal consideration of the combining together of contents of certificates is given in section 1 of the Appendix forming the final part of this description. In particular, section 1, Appendix A treats both the delegation rule for combining 5-tuples formed by the contents of attribute certificates, and the naming rule for name mapping using 4-tuples formed by the contents of name certificates. The tuple representations used in the Appendix and at other places in this description are of the form:    5-tuple: <i,s,a,d,v> where i, s, a, d, v respectively correspond to the issuer, subject, authorisation, delegation and validity fields of an attribute certificate, and    4-tuple: <i.n=s,v> where i, n, s, v correspond to issuer, name, subject and validity of a name certificate.
(It will be appreciated that the corresponding graphical representations of certificate contents in the accompanying drawings are less formal, for example the contents of an attribute certificate are generally shown as an arrow from the issuer to the subject, omitting the delegation and validity elements and, where required for clarity, also the authorisation element—which, if present, is placed alongside by the arrow).
Proving a trust chain from the contents of certificates is relatively straight forward if the proving engine is presented with the correct certificates (or, rather, their contents) in the order required. However determining what certificates should be presented may not be a trivial task—it may be necessary to select the required certificates from hundreds of available ones. The task of choosing the certificates, sometimes referred to as “certificate path discovery”, is discussed in the MIT Masters thesis of Jean-Emile Elien (reference[7]). However, the thesis concentrates on name rewriting only, and does not explain how SPKI tags (authorisations) containing patterns are dealt with. The treatment of name certificates as a rewriting system by computing the transitive closure has complexity of the order of the cube of the number of certificates which is likely to be impractical.
It is an object of the present invention to provide an improved method and apparatus for seeking a trust chain by which a subject is delegated a particular attribute, starting with a collection of certificates not all of which may be relevant.